package com.leetcode.partition14;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/1/21 18:56
 */
public class LC1345跳跃游戏IV_双向bfs {

    private static final int N = (int) (5e4 + 10), INF = 0x3f3f3f3f;
    private static Map<Integer, List<Integer>> map = new HashMap<>();

    private static int[] arr, dist1 = new int[N], dist2 = new int[N];
    private static Queue<Integer> queue1 = new ArrayDeque<>(N), queue2 = new ArrayDeque<>(N);

    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int[] arr = new int[s.length];
        for (int i = 0; i < s.length; i++) arr[i] = Integer.parseInt(s[i]);
        writer.write(minJumps(arr) + "\n");
        writer.flush();
    }

    public static int minJumps(int[] array) {
        arr = array;
        n = arr.length;
        if (n == 1) return 0;
        //类似于建图，每个节点的一对多的关系
        for (int i = n - 1; i >= 0; i--) {
            List<Integer> indices = map.getOrDefault(arr[i], new ArrayList<>());
            indices.add(i);
            map.put(arr[i], indices);
        }
        for (int i = 0; i < N; i++) dist1[i] = dist2[i] = INF;
        dist1[0] = 0;
        queue1.add(0);
        dist2[n - 1] = 0;
        queue2.add(n - 1);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int ans = queue1.size() >= queue2.size() ? search(queue1, dist1, dist2) : search(queue2, dist2, dist1);
            if (ans != -1) return ans;
        }
        return -1;
    }

    private static int search(Queue<Integer> queue1, int[] dist1, int[] dist2) {
        int m = queue1.size();
        while (m-- > 0) {
            int u = queue1.poll(), w = dist1[u];
            if (u + 1 < n) {
                if (dist2[u + 1] != INF) return dist2[u + 1] + 1 + w;
                if (dist1[u + 1] == INF) {
                    queue1.add(u + 1);
                    dist1[u + 1] = w + 1;
                }
            }
            if (u - 1 >= 0) {
                if (dist2[u - 1] != INF) return dist2[u - 1] + 1 + w;
                if (dist1[u - 1] == INF) {
                    queue1.add(u - 1);
                    dist1[u - 1] = w + 1;
                }
            }
            List<Integer> next = map.getOrDefault(arr[u], null);
            if (next == null) return -1;
            for (int v : next) {
                if (dist2[v] != INF) return w + 1 + dist2[v];
                if (dist1[v] == INF) {
                    queue1.add(v);
                    dist1[v] = w + 1;
                }
            }
            map.remove(arr[u]);
        }
        return -1;
    }
}
